package com.kevinkk.greedy;

/**
 * 给定一个二叉树，我们在树的节点上安装摄像头。
 * 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
 * 计算监控树的所有节点所需的最小摄像头数量。
 *
 * 0 表示未覆盖
 * 1 表示覆盖
 * 2 表示安装了摄像头
 * 从底向上遍历
 */

public class BinaryTreeCameras {
    class Solution {
        int count = 0;
        public int minCameraCover(TreeNode root) {
            // 后序遍历，如果最后的根节点没有覆盖的话，还需要在根节点处再放一个摄像头
            if (traversal(root) == 0)
                count++;
            return count;
        }

        private int traversal(TreeNode root) {
            // 空节点默认是被覆盖了
            if (root == null) return 1;
            // 后序遍历
            int left = traversal(root.left);
            int right = traversal(root.right);

            // 叶子节点没有被覆盖（不在叶子节点放摄像头）
            if (left == 1 && right == 1) return 0;
            // 如果有一个叶子节点没有被覆盖，那么就需要放置一个摄像头
            if (left == 0 || right == 0) {
                count++;
                return 2;
            }
            // 有一个叶子节点放了摄像头，那么它的父节点肯定被覆盖到了
            if (left == 2 || right == 2) return 1;
            return -1;
        }
    }
}
